package Z代码随想录.数组;

import java.util.Arrays;

public class Leetcode34 {
// 此处要考虑四种情况
    // 1，如果目标值大于最大值，或者 小于最小值，则返回[-1,-1]
    // 2. 如果数组为空，则返回[-1,-1]
    // 3. 如果目标值不存在数组中，则返回 [-1,-1]
    // 4. 如果目标值在数组中，则返回 数组下标范围

    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums,target);
        int rightBorder = getRightBorder(nums,target);
        // 第一种情况就是数组元素都比目标值小，右边界始终未默认值-2，  数组元素都比目标值大，左边界还是为-2默认值
        if(leftBorder == -2 || rightBorder == -2){
            return new int[]{-1,-1};
        }
        // 第二种情况就是数组内找到 target值
        if ((rightBorder - leftBorder) > 1){
            return new int[]{leftBorder+1,rightBorder-1};
        }
        // 剩下的就数组内找不到目标值，和数组为空的情况
        return new int[]{-1,-1};

    }

    // 此处额外写两个找边界的代码，一个是找到左边界，一个是右边界

    // 寻找左边界
    public static int getLeftBorder(int[] nums, int target) {
        // 默认边界为-2，表示未找到 target
        int leftBorder = -2;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 此处要寻找左边界，所以mid 大于等于 target 的时候，仍然要往左边寻找是否还有 等于 target的值，找到数组中比目标值小的最大数
            if (target <= nums[mid]) {
                right = mid - 1;
                // 将left的值赋值给 leftBorder
                leftBorder = right;
            } else {
                // 此时 target的值大于 mid, 就往右边寻找
                left = mid + 1;
            }
        }
        return leftBorder;
    }

    // 寻找右边界
    public static int getRightBorder(int[] nums, int target) {
        // 默认边界值为 -2，表示未找到 target
        int rightBorder = -2;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 此处寻找右边界，当目标值 大于等于 mid 值，需要继续右边寻找,找到数组中比目标值大的最小数
            if (target >= nums[mid]) {
                left = mid + 1;
                rightBorder = left;
            }else {
                right = mid - 1;
            }
        }
        return rightBorder;
    }
}
